%%This is a very basic article template.
%%There is just one section and two subsections.
\documentclass{article}

\usepackage{amsmath, listings}
\usepackage[pdftex]{graphicx}
\usepackage{algorithmic, algorithm}
\newcommand{\pre}{\texttt}
\newcommand{\property}[1]{\begin{quotation}\emph{#1}\end{quotation}}
\newcommand{\formula}[1]{\vspace{2mm}\\\vspace{2mm}\setlength\arraycolsep{1.5em}$\begin{array}[b]{l}#1\end{array}$}

\begin{document}

\section{Introduction}

\subsection{Domain-Specific Languages}

The DSL approach has long been used with great success in many
domains, from the telephony to web application development. Unlike
general-purpose programming languages, their goal is to provide a
restricted vocabulary that is adapted to the domain for which they
are dedicated, and thus target experts in that domain. Required
programming expertise vary according either to either the domain of
DSL, its vocabulary or its syntax. Popular DSLs are SQL (Structured
Query Language), specific to the manipulation of relational
databases, or GraphViz, a language to write graphs.

There exists two forms of implementation of a DSL, that are either
embedding a DSL into an existing language or designing a standalone
DSL (TODO: find refs.). Embedded DSLs leverage the existing concepts
of general-purpose language and the various tools that are developed
for them. They are particularly suited to design DSLs whose target
is programmers that are already familiar to paradigms of the
embedding language. Conversely, standalone DSLs find advantages in
the fact that they are not constrained to the semantics of an
existing language that can be hard to override. Moreover, DSLs are
not only dedicated to experienced programmers. We can find
interesting examples in visual languages, like Scratch, developed by
MIT Lab. Scratch is a visual language that targets children, and
which domain is the design of animations or small games.

Advantages of DSL include the following:

\begin{itemize}
\item Language vocabulary is close to the domain expert vocabulary, therefore
more concise than general-purpose languages.
\item Verification is easier, and properties like Termination can become
decidable.
\end{itemize}

Other advantages can be found on the literature but these two are
the advantages that we are interested in.


\subsection{Pantagruel: a visual DSL for prototyping ubiquitous applications}


Ubiquitous computing is a domain that has become popular for recent
years, with the proliferation of remotely accessible, networked
devices that become programmable and interoperable. Networks of such
devices are deployed in various areas that we call ubiquitous
environments (or smart spaces). These environments aim at providing
various services to people living in there. A classic example is
home assistance e.g managing lights, heat, or helping residents in
their everyday-life activities by e.g. automating some of their
usual tasks.

Ubiquitous computing concerns different kinds of people, from
distributed computing experts to the end-users, i.e people living in
an ubiquitous environment. Therefore integrating DSL into this area
sounds accurate, in particular regarding end-users, since they can
now become programmers of their environment.

This motivated us to propose Pantagruel, a domain specific language
for prototyping ubiquitous application at an early stage of design.
Actually we do not directly target end-users, but designers whose
work is close to end-users and directly related to their
requirements. We place our language on early design stage where
end-user holds an important place. Therefore we introduced in our
language very high-level concepts that abstract over heterogeneity
of entities and intricacies of distributed computing.

Pantagruel is a rule-based language for prototyping ubiquitous
applications in two steps: first, the programmer defines an
environment as a collection of entity classes and their instances,
provided with their characteristics and functionalities. Second, the
programmer defines an orchestration logic on the instances. We won't
get deep in the details of this process. We will focus on this paper
on Pantagruel semantics, that specifies the execution process of the
orchestration logic. Before that, we rapidly introduce the concepts
of our language:

\paragraph{Entity classes.} Entity classes are abstractions of entities
that are contained in a pervasive environment. An entity class
consists of attributes defining a state and method interfacess to
invoke external operations. Attributes and methods are attached
annotations declaring information on their behavior. These classes
represent the building blocks required to define a coordination
scenario. An instance of an entity class is an entity for which
constant attributes are initialized.

\paragraph{Orchestration logic.} An orchestration logic or scenario consists of
a set of rules. Each rule has three parts: (1) a sensor, defining a
condition to trigger the rule, (2) a controller, combining sensors,
and (3) an actuator, performing some actions. In the following
section, we describe more precisely entity classes and the
orchestration logic.

\subsubsection{Definition of entity classes}

In this step, we build the taxonomy of entities that we want to
orchestrate. The taxonomy consists of a set of entity classes that
are hierarchically related to each other. Each class consists of
attributes and methods. There is a root class called \emph{Entity}
of which all entities inherit directly or indirectly. This hierarchy
allow reuse of attributes and methods

\paragraph{Attributes}

A class can have three kinds of attributes.  We refer to these kinds
with \emph{constant}, \emph{volatile}, and \emph{write} modifiers.
Attributes are typed with primitive types (Integer, String, Boolean)
or user-defined enumerations.

\begin{itemize}
\item\emph{Constant attributes} are the variation points
between the instances of a given class. They represent fixed
characteristics that do not evolve across time.

\item\emph{Volatile attributes} abstract changes
of an entity characteristics whose origin comes from outside the
program. They represent data resulting from a reaction to external
stimuli.

\item\emph{Write attributes} represent the result of internal reactions
(i.e. internal occurring events) of the system described by
Pantagruel scenarios. These variables are modified by methods that
declare them as \emph{effects}, as mentioned in next paragraph.
\end{itemize}


\paragraph{Methods}

Methods refer to external functions defined in external libraries of
Pantagruel runtime layer. It is not the role of Pantagruel to define
the behavior of these methods, but only to provide their
side-effects so that the designer of the orchestration logic is
aware of the effects a method can have on a Pantagruel program's
behavior. Methods can only modify \emph{write} attributes.
Therefore, the side-effects of a method are a set of write
attributes that belong to the method's class. A method can have
parameters.

\subsubsection{Defining an orchestration logic}

Once a set of entity classes are defined as well as a collection of
instances, we can define the orchestration logic (= scenario). The
scenario describes the behavior of instances according to some
conditions in the form of rules. This part of Pantagruel borrows
heavily from Blender Game Engine\footnote{http://www.blender.org}, a
software for designing games and dedicated to novice- either
non-programmers.

A pantagruel scenario consists of defining a set of rules following
a paradigm called sensor-controller-actuator. A rule is a collection
of sensors that are combined with a controller. These sensors are
also connected to a set of actuators using this controller. Each
sensor is a condition on the attribute of an entity (or entity
class), and each actuator is a method invocation, and a controller
is a OR or AND logic operator: conditions in a rule can be pure
conjunctions or pure disjunctions, i.e they respectively all must be
satisfied, or only one of them, to trigger the actions execution. In
summary, all the methods used in a rule are executed when one or all
(depending on the controller) of the conditions of this rule are
satisfied (we give details of the rule execution process in Section
\ref{characteristics}).

\section{Pantagruel Characteristics}
\label{characteristics}

\subsection{A formalized representation of Pantagruel}

In order to be able to reason on Pantagruel, we propose here a
simplified formalization of the concepts we introduced in the
previous section. In particular, we do not take in account the
notion of entity classes and entities. Instead, we will reason on
attributes as simple variables of the three mentioned kinds write,
volatile, and constant.

\paragraph{Scenario} A scenario is a set of n rules noted as
$\displaystyle \bigcup_{i \in [0..n]} R_i$

\paragraph{Rule} We formulate a rule R$_i$ (i$^{th}$ rule of a scenario) as
following: \property{$R_i:S_i \xrightarrow{c_i} A_i$} $S_i$ denotes
a set of sensors, $A_i$ denotes a set of actuators, and $c_i$
denotes a controller that combines $S_i$ elements and connect them
to $A_i$.


\paragraph{Controller} One controller matches one rule. A controller
$c$ is a boolean operator i.e \pre{AND} or \pre{OR}. If $c$ equals
\pre{AND}: when all the sensors in $S$ are true, then all the
actuators in $A$ are triggered. If $c$ equals \pre{OR}: if at least
one of the sensors in $S$ is true, then all actuators in $A$ are
triggered. If there is only one sensor in a rule, choosing one or
the other operator does not make a difference. This controller can
easily be extended by new operators (NotAND, NotOR, XOR...), but we
won't consider them because they don't add interesting information
for our study. There is a specific kind of controller called a
sequenced controller. This controller makes explicit an order of
execution of the actuators. However we won't consider this case that
brings nothing to our study.

\paragraph{Sensor} A sensor is a
predicate. A predicate is a boolean expression that tests the value
of a variable. In a scenario, the evaluation of the whole set of
sensors of all rules denotes the overall state of the scenario at a
discrete time $t$. Formally written, $pred\_eval_t(\displaystyle
\bigcup_i S_i) =$ state of the scenario.

A predicate has these forms:
\begin{itemize}
  \item $x$ \pre{OPERATOR} $y$, where  $x$ is the name of a
variable, \verb+OPERATOR+ is a binary operator among $<, =, \neq, >$
or $\in$ for enumerations, and $y$ is the name of either a variable
or a value which type is equivalent to $x$'s type.
 \item{$x$ \textbf{changed}}: this condition is true if $x$ changed from time
 $t-1$ to $t$.
\end{itemize}

\paragraph{Actuator} An actuator is a call to a method. The behavior of the
method is unknown (because it refers to an external function). It
can be provided with parameters, and can have side-effects. However,
We can define the function $effect_r(R_i) = \displaystyle \bigcup_{a
\in A_i} effect(a)$ where $effect(a) = \{x_1,...,x_n\}$ are the
side-effects of actuator $a$. An actuator can have no effect (i.e.
$effect(a) = \emptyset$ is allowed) The $x_i$ are the names of the
write variables affected by $a$. For convenience, we will write $a$
as $a:\{x_1,...,x_n\}$.


\subsection{Pantagruel Dynamic Semantics: an Overview}

Pantagruel semantics has been formally defined. We show here an
overview of its dynamic semantics, that is its process of execution

\subsubsection{Hypotheses and definitions}

Pantagruel is a simplified reactive system. Before explaining its
dynamic semantics, i.e the execution process of a Pantagruel
program, we lay down the following hypotheses and definitions:

\begin{itemize}
  \item The execution of a method is atomic: once it is run, a method
  finishes immediately.
  \item A rule is said \emph{true} if all its predicates are true
  \item A rule is said \emph{active} at a logic time $t$ if its predicates are
  true at $t$, and if this rule was false at $t-1$. Otherwise it is inactive.
  We 'extend' this notion of \emph{activeness} for predicates: a predicate is
  \emph{active} if it is true at $t$, whereas it was false at $t-1$.
\end{itemize}


\subsubsection{Description of the behavior}


Executing a Pantagruel program (=scenario) consists of invoking the
methods of all rules according to a global context. This context is
a store, containing the values of all the variables at a given logic
time $t$. We propose a simplified mechanism that circumvent
potential issues of concurrency that are not the purpose of our
approach. This mechanism is an infinite loop, inside which all the
rules of a scenario are sequentially evaluated. The evaluation
involves 2 stores: first one (say $s_0$) is used to evaluate the
predicates of all the rules, making active some of these rules , and
inactive the others. Second store ($s_1$), which equals $s_0$ at the
begining of an iteration of the loop, is updated each time a rule is
triggered, if this rule has methods with side-effects. At the end of
an iteration, $s_0$ is replaced by $s_1$ and the process begins
agains.

(\textbf{fixme: i am not sure that it is interesting to talk about
this here:} Because of the sequential evaluation of rules, there is
no notion of conflict between rules in a Pantagruel program: if two
rules that have the same method(s) are active at the same time, the
method(s) is (are) run twice - i.e the second method evaluation may
override the side-effects of the first one. Or, if a method is a
counter on a variable $x$ (e.g. $increment(x)$), than x is updated
to x+2.)

The algorithm \ref{algorithm} describes the execution process of a
Pantagruel scenario. We explain the $eval\_rule$, $update\_state$
and $update\_volatile$ functions in the following subsections.

\begin{algorithm}
\caption{Overview of Pantagruel program algorithm} \label{algorithm}
\begin{algorithmic}[1]
\STATE Let $R =\{r_1, \ldots, r_n\}$ be the set of rules of a given
scenario. \STATE Let $s, s_0$ 2 stores containing all variables used
in Pantagruel program. Initially, $s = s_0$. $s$ is a set of tuples
$(varname, value)$, where $varname$ is the name of a variable, and
$value$ its value. All constant variables have a defined $value$.
For all write and volatile variables, $value$ initially equals
$\perp$ \STATE Let $e_{sc}, e_s$ be resp. the service class
environment and the service instance environment. \STATE Let
$\sigma$ be a predicate state containing the state of all
predicates. $\sigma$ is a set of tuples $(predicate, bvalue)$, where
$bvalue$ is either a boolean or a value which type is the type of
the variable tested by the predicate. If the predicate is of the
form \pre{x OPERATOR y}, then $bvalue$ is a boolean value. If the
predicate is of the from $x$ \textbf{changed}, then $bvalue$ is a
value which type equals $x$'s type. $bvalue$ initially equals
$false$ or $\perp$, for all the predicates.

\WHILE{true}

\FORALL{$r_i \in R$} \STATE $s \leftarrow eval\_rule(r_i, e_{sc},
e_s, \sigma, s_0, s)$ \ENDFOR \STATE $\sigma \leftarrow
update\_state(\sigma, s_0)$ \STATE $s \leftarrow update\_volatile(V,
s)$ where $V$ is the set of all volatile attributes. \STATE $s_0
\leftarrow copy(s)$ \ENDWHILE
\end{algorithmic}\end{algorithm}

We partly describe below the functions used in this algorithm. In
the sequel, we will use the following notations: $Pred(r)$ is the
set of predicates used in rule $r$, $Meth(r)$ is the set of methods
used in rule $r$.


\begin{itemize}
  \item $update\_state$: for each tuple $state\_tuple = (predicate,
  bvalue) \in \sigma$, $predicate$ is evaluated using variables values stored
  into $s_0$. For convenience, we will define $state$ a function such that
  $state: p \to state\_tuple$, and $state(p) =$ state of
  predicate $p$ in $\sigma$.
  \item $eval\_rule$: \\
  let's call $eval\_p$ a function such that \\ $eval\_p : predicate \to
  Boolean$, and such that $eval\_p$ returns true if $p$ is true according to
  $s_0$, false otherwise.
  \\Let's also call $active\_p$ a function such that \\
  $active\_p : predicate \to Boolean$, and $active\_p(p)$ returns true if a
  predicate $p$ is \emph{active}, false otherwise. This means that if $p$ is of the form
  ``\pre{x OPERATOR y}'', and if $state(p) = (p, false)$, and if $eval\_p(p) =
  true$, then we have $active\_p(p) = true$. Otherwise $active\_p(p) = false$.
  Besides, if $p$ is of the form ``\pre{x \textbf{changed}}'' and $state(p) = v$, and $x \neq v$ in $s_0$, $active\_p(p)
  = true$ (false otherwise).
   Consequently, if, $\forall p \in $ $Pred(r_i), eval\_p(p)=true$,
  $\exists p_k \in Pred(r_i)$, such that $active\_p(p_k) = true$, then all
  methods $m \in Meth(r_i)$ are executed and the store $s$ is updated with
  the side-effects of $m$.
  \item $update\_volatile$: this function updates store $s$ with the value of
  volatile variable $V$ given in its argument by calling an external function
  that ``provides'' a value for $V$. This external function can be seen as a
  function that regularly checks for volatile variables coming from ``outside'', e.g. a
  function that read keyboard inputs. The definition of this function is not
  part of Pantagruel semantics, but rather of its implementation, which is
  not the purpose of this document.
\end{itemize}

\end{document}
